package cn.edu.zufe.mjt.recursion;

/**
 * 递归问题——斐波那契数列
 * 递归是一种函数调用自己的编程技巧。递归的基本思想是将一个复杂的问题分解为更简单的子问题直到子问题的规模足够小，能够直接解决。递归通常由两个部分组成:
 * 终止条件:递归的终止条件，防止无限递归。
 * 递归调用:将当前问题转化为更小规模的同类问题，并在其上进行求解。
 * 斐波那契数列定义如下：
 *       F(0) = 0
 *       F(1) = 1
 *       F(n) = F(n-1) + F(n-2) (n>=2)
 */
public class Fibonacci {
    public static void main(String[] args) {
        long startTime;
        long endTime ;
        for (int i = 1; i < 45; i++) {
            startTime = System.currentTimeMillis();
            System.out.println(fibonacci(i));
            endTime = System.currentTimeMillis();
            System.out.println("第" + i + "次耗时: " + (endTime - startTime) + " ms");
        }
    }

    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }
}
